Udeshi Salgado
Data Lab for Social Good,
Cardiff University, UK
2025-05-17
A continuous-time Markov chain is a stochastic process
\[ \{X(t) \mid t \geq 0\} \]
in which the probability of some future event (say ( A )) depends only on the current state, not on past states.
Formally:
\[ \Pr(A \mid X(t),\, 0 \leq t \leq T) = \Pr(A \mid X(T)) \]
As in the discrete-time case, the key idea is: future behavior depends only on the current state.
Imagine a small neighborhood pharmacy with space for maximum of two customers at a time. As the shop owner, you’re analyzing foot traffic to optimize customer experience without overcrowding or turning people away.
0, 1, and 2.Let \(T_i\) be the time until the next transition from state \(i \in \{0, 1, 2\}\)
\(T_0 \sim \text{Exp}(1)\) (arrival triggers transition)
\(T_2 \sim \text{Exp}(0.5)\) (departure triggers transition)
\(T_1 = \min(A, D)\), where:
Suppose \(T_1\), \(T_2\) are independent and \[ T_1 \sim \text{Exp}(\lambda_1),\quad T_2 \sim \text{Exp}(\lambda_2) \]
Then:
\[
\min(T_1, T_2) \sim \text{Exp}(\lambda_1 + \lambda_2)
\]
Application to our example:
The generator matrix (Q) summarizes the transition rates between states in a CTMC.
Steady-state probabilities represent the long-run behavior of the system.
They tell us:
To find them, we solve: \[ \boldsymbol{\pi} \mathbf{Q} = \mathbf{0}, \quad \text{with} \quad \sum \pi_i = 1 \]
From:
Thus: \[ \pi_0 = \frac{1}{13},\quad \pi_1 = \frac{4}{13},\quad \pi_2 = \frac{8}{13} \]
We calculate:
\[ 0 \cdot \frac{1}{13} + 1 \cdot \frac{4}{13} + 2 \cdot \frac{8}{13} = \frac{20}{13} \approx 1.54 \]
This is the expected number of customers in the shop in the long run.
A queueing system (e.g., customer service desk, call center, clinic) can often be modeled as a continuous-time Markov chain, under assumptions like:
Welcome to Queueing Theory!
We’ll explore how to model and analyze systems where “waiting” happens — like hospitals, call centers, and shops.
A system with:
Queueing systems are described using: A/B/S/d/e
Example: M/M/2/5/FIFO
→ Exponential arrivals, exponential service, 2 servers,
→ Max 5 customers in system, served in order of arrival
Definition:
A Poisson process with rate \(\lambda\) models random arrivals over time, where:
Traffic intensity:
\[
\rho = \frac{\lambda}{\mu}
\]
💡 Think of \(\rho\) as the load on the server.
If arrivals outpace service, the system can’t cope.
The M/M/1 queue can be modeled as a Continuous-Time Markov Chain (CTMC) with states representing the number of customers in the system.
It forms a birth-death process:
Generator matrix (Q):
\[ \mathbf{Q} = \begin{pmatrix} -\lambda & \lambda & 0 & 0 & \cdots \\ \mu & -(\lambda + \mu) & \lambda & 0 & \cdots \\ 0 & \mu & -(\lambda + \mu) & \lambda & \cdots \\ \vdots & \vdots & \ddots & \ddots & \ddots \end{pmatrix} \]
With steady-state probabilities \(\{p_n,\ n \geq 0\}\):
Mean number of customers in the system (L):
\[ L = \sum_{n=0}^\infty n p_n = (1 - \rho) \sum_{n=0}^\infty n \rho^n = \frac{\rho}{1 - \rho} \]
This is one of the key performance metrics in queueing theory.
Four key summary performance measures:
A fundamental relationship linking arrival rate, waiting time, and number in the system.
Relates these measures:
\[ L = \lambda W,\quad L_q = \lambda W_q \]
Also:
\[ W = W_q + \frac{1}{\mu},\quad L = L_q + \frac{\lambda}{\mu} \]
Using \(\rho = \frac{\lambda}{\mu}\) and Little’s Law:
Mean number in the system: \[ L = \frac{\rho}{1 - \rho} \]
Mean number in queue: \[ L_q = \frac{\rho^2}{1 - \rho} \]
Mean time in the system: \[ W = \frac{1}{\mu(1 - \rho)} \]
Mean waiting time in queue: \[ W_q = \frac{\rho}{\mu(1 - \rho)} \]
| Feature | M/M/1 | M/M/s | M/M/s/b |
|---|---|---|---|
| Servers | 1 | \(s\) | \(s\) |
| System Capacity | Infinite | Infinite | \(b\) (finite) |
| Arrival Rate (\(\lambda\)) | Poisson | Poisson | Poisson |
| Service Time | Exponential | Exponential | Exponential |
| Queue Capacity | Infinite | Infinite | \(b - s\) |
| Blocking? | No | No | Yes (if system full) |
| Common Use | Basic single-server queue | Multi-server (e.g., call center) | Limited capacity (e.g., hospital beds) |
You’ll see 3 real-world situations.
For each one, pick the most suitable queueing model:
You’ll have 30 seconds to discuss or decide for each!
An emergency care unit in a district hospital has five treatment beds. Once all beds are occupied, incoming patients must be transferred to a different facility, as there is no space for waiting or holding.
Which queueing model applies?
M/M/s/b Queueing Model
- Multiple beds = multiple servers
- No waiting space = limited capacity
- Incoming patients are blocked if full
A mobile vaccination clinic is staffed by a single nurse. Patients from a rural community arrive randomly and are vaccinated one at a time. If the nurse is busy, others wait in line without any restrictions on queue length.
Which model applies?
M/M/1 Queueing Model
A city hospital’s diagnostic laboratory operates with four technicians. Incoming test samples are processed as soon as a technician is free. If all are busy, samples wait in a queue with no limit.
Which model applies?
M/M/s Queueing Model
In this hands-on session, you’ll use R code to explore how Continuous-Time Markov Chains (CTMCs) and Queueing Theory help us understand operations at a rural vaccine clinic.
We’ll work through:
Make sure R and the necessary libraries are ready (e.g.,
Matrix,expm).
You’ll be guided with real-world tasks followed by code. Let’s begin!
© 2025 Udeshi Salgado – DL4SG, Cardiff University